import java.util.Deque;
import java.util.LinkedList;

public class Solution678 {
    public boolean checkValidString(String s) {
        char[] str = s.toCharArray();
        Deque<Integer> kuohao = new LinkedList<>();
        Deque<Integer> xing=new LinkedList<>();

        for (int i = 0; i < str.length; i++) {
            if (str[i] == '(') kuohao.push(i);
            else if (str[i] == '*') xing.push(i);
            else{
                if(!kuohao.isEmpty())
                    kuohao.pop();
                else if(!xing.isEmpty()){
                    xing.pop();
                }
                else {
                    return false;
                }
            }
        }

        while(!kuohao.isEmpty() && !xing.isEmpty()){
            int leftIndex = kuohao.pop();
            int asteriskIndex = xing.pop();
            if (leftIndex > asteriskIndex) {
                return false;
            }
        }
        return kuohao.isEmpty();
    }

    public static void main(String[] args) {
        Solution678 solution678 = new Solution678();
        System.out.println(solution678.
                checkValidString("((((()(()()()*()(((((*)()*(**(())))))(())()())(((())())())))))))(((((())*)))()))(()((*()*(*)))(*)()"));
    }
}
